package acm.pta13;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.*;
import java.util.function.Function;

// dj+反向边+暴力枚举+树状数组求区间最小值（有点难度）

/**
 * todo: 有问题，技巧难题
 * 思路：
 * 1.枚举从起点到所有点的最短money路径
 * 2.枚举从终点到所有点的最短coin路径
 * 尝试从每个点作为中转点，到达该点后兑换货币，再从该点到终点。记录下每个点的现金值，取最小值
 */
public class 森森旅游 {
    static Node[] nodes;
    static long[] moneys;
    static long[] coins;
    static int n;
    static int m;
    static int k;
    static final Function<Edge, Integer> byMoney = edge -> edge.money;
    static final Function<Edge, Integer> byCoin = edge -> edge.coin;
    static final Function<Node, List<Edge>> forward = node -> node.nexts;
    static final Function<Node, List<Edge>> backwards = node -> node.pres;

    public static void main(String[] args) {
        Reader sc = new Reader();
        n = sc.nextInt();
        m = sc.nextInt();
        k = sc.nextInt();
        nodes = new Node[n + 1];
        for (int i = 1; i <= n; i++) {
            nodes[i] = new Node(i);
        }
        for (int i = 0; i < m; i++) {
            int from = sc.nextInt();
            int to = sc.nextInt();
            int money = sc.nextInt();
            int coin = sc.nextInt();
            nodes[from].nexts.add(new Edge(nodes[from], nodes[to], money, coin));   //正向边
            nodes[to].pres.add(new Edge(nodes[to], nodes[from], money, coin));  //反向边
        }
        for (int i = 1; i <= n; i++) {
            nodes[i].cash = sc.nextInt();
        }
        moneys = dijkstra(1, forward, byMoney);
        coins = dijkstra(n, backwards, byCoin);
        TreeArray treeArray = new TreeArray();
        for (int i = 0; i < k; i++) {
            int index = sc.nextInt();
            nodes[index].cash = sc.nextInt();
            treeArray.update(index);
            System.out.println(treeArray.query(n));
        }
    }

    /**
     * 4 3 1
     * 1 2 1 1
     * 1 3 5 5
     * 3 1 10 10
     * 2 100 1 1
     */
    static class TreeArray {
        long[] tree;
        long[] origin;
        long min = Long.MAX_VALUE;

        public TreeArray() {
            tree = new long[moneys.length];
            origin = new long[moneys.length];
            Arrays.fill(origin, Long.MAX_VALUE);
            tree[0] = Long.MAX_VALUE;
            for (int i = 1; i < tree.length; i++) {
                if (moneys[i] != Long.MAX_VALUE && coins[i] != Long.MAX_VALUE) {
                    origin[i] = moneys[i] + (long) Math.ceil(1.0 * coins[i] / nodes[i].cash);
                }
                update(i);
            }
        }

        public void update(int index) {
            int i = index;
            boolean flag = origin[i] == min; //修改的是否是min
            if (origin[i] != Long.MAX_VALUE) {
                origin[i] = moneys[i] + (long) Math.ceil(1.0 * coins[i] / nodes[i].cash);
            }
            while (i < tree.length) {
                tree[i] = origin[i];
                int x = lowbit(i);
                for (int j = 1; j < x; j++) { //更新管辖区间的最小值
                    tree[i] = Math.min(tree[i], tree[i - j]);
                }
                i += i & -i;
            }
            if (flag&&origin[index]!=Long.MAX_VALUE) min = query(n);
            else min = Math.min(min, origin[index]);
        }

        public long query(int n) {
            long min = Long.MAX_VALUE; // 初始化最小值为最大值
            while (n > 0) { // 当n大于0时，继续查询
                min = Math.min(min, tree[n]); // 更新最小值
                n -= lowbit(n); // 更新n的值
            }
            return min; // 返回最小值
        }

        public int lowbit(int x) {
            return x & -x;
        }
    }

    public static long[] select(long[] moneys, long[] coins) {
        long[] min = {0, Long.MAX_VALUE};    //所需最小money
        for (int i = 1; i <= n; i++) {  //枚举在每个节点兑换金币需要的money
            if (coins[i] == Long.MAX_VALUE || moneys[i] == Long.MAX_VALUE) continue;  //不可达
            long cur = moneys[i] + (long) Math.ceil(1.0 * coins[i] / nodes[i].cash);
            if (cur < min[1]) {
                min[0] = i;
                min[1] = cur;
            }
        }
        return min;
    }

    /**
     * 从起点到每个点的最短money路径
     *
     * @param s
     * @param direction 选择正向或者反向
     * @param by        选择money或者coin获取最短路径
     * @return
     */
    public static long[] dijkstra(int s, Function<Node, List<Edge>> direction, Function<Edge, Integer> by) {
        long[] info = {s, 0}; //当前点信息,0:id,1:所需money
        long[] res = new long[n + 1];    //记录每个点的最短money路径
        Arrays.fill(res, Long.MAX_VALUE);
        boolean[] vis = new boolean[nodes.length];
        //根据money升序
        PriorityQueue<long[]> queue = new PriorityQueue<>(Comparator.comparingLong(o -> o[1]));
        int count = 0;    //记录已访问点数
        queue.add(info);
        while (count < n && !queue.isEmpty()) {
            info = queue.poll();
            int id = (int) info[0];
            if (vis[id]) continue;
            res[id] = info[1];
            vis[id] = true;
            count++;
            Node curr = nodes[id];
            for (Edge edge : direction.apply(curr)) {
                Node to = edge.to;
                long newPath = info[1] + by.apply(edge);
                if (vis[to.id] || newPath >= res[to.id]) continue;    //被访问过或者超过最短money路径直接跳过
                res[to.id] = newPath;
                queue.add(new long[]{to.id, newPath});
            }
        }
        return res;
    }


    static class Node {
        int id;
        int cash;   //汇率
        List<Edge> nexts = new LinkedList<>();  //出边
        List<Edge> pres = new LinkedList<>();   //入边

        public Node(int id) {
            this.id = id;
        }

        @Override
        public String toString() {
            return "Node{" +
                    "id=" + id +
                    ", cash=" + cash +
                    '}';
        }
    }

    static class Edge {
        Node from;
        Node to;
        int money;  //所需现金
        int coin;   //所需货币

        public Edge(Node from, Node to, int money, int coin) {
            this.from = from;
            this.to = to;
            this.money = money;
            this.coin = coin;
        }

        @Override
        public String toString() {
            return from.id + "->" + to.id + " " + money + " " + coin;
        }
    }

    static class Reader {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

        public int nextInt() {
            try {
                in.nextToken();
            } catch (Exception ignored) {
            }
            return (int) in.nval;
        }
    }
}
